#pragma once
#include "BTreeNode.h"

namespace BTreeDetail
{
	template <typename Key, size_t Deg> requires MinDeg<Deg>
	DataNode<Key, Deg>::DataNode(POwnerPtr ppOwner)
	{
		_ppOwner = ppOwner;
		_ppSelf = std::make_shared<DataNode*>(this);
		_ppLeft = std::make_shared<InnNode*>();
		_ppRight = std::make_shared<InnNode*>();
	}

	template <typename Key, size_t Deg> requires MinDeg<Deg>
	DataNode<Key, Deg>::~DataNode()
	{
		*_ppSelf = nullptr;
	}

	template <typename Key, size_t Deg> requires MinDeg<Deg>
	auto DataNode<Key, Deg>::merge()->InnNode*
	{
		if (!_ppParent || !*_ppParent)
			return NULL;

		if (!_ppLeft || !*_ppLeft)
			return NULL;

		if (!_ppRight || !*_ppRight)
			return NULL;

		InnNode& left = **_ppLeft;
		if (left._data.size() > SplitDeg<Deg>)
			return NULL;

		PInnNodePtr tmpRight = _ppRight;
		InnNode& right = **tmpRight;
		if (right._data.size() > SplitDeg<Deg>)
			return NULL;

		left._ppRight = right._ppRight;
		if (*left._ppRight)
			(*left._ppRight)->_ppLeft = left._ppSelf;

		left._data.splice(left._data.end(), (*_ppParent)->_data, _id);
		_ppParent = left._ppSelf;
		_ppLeft = (*left._data.rbegin())->_ppRight;
		_ppRight = (*right._data.begin())->_ppLeft;

		bool first = true;
		for (auto pNode : right._data)
		{
			DataNode& tmpNode = *pNode;
			tmpNode._ppParent = left._ppSelf;
			if (right._leaf)
				continue;

			(*tmpNode._ppRight)->_ppParent = left._ppSelf;
			if (!first)
				continue;

			first = false;
			(*tmpNode._ppLeft)->_ppParent = left._ppSelf;
		}

		left._data.splice(left._data.end(), right._data);
		DEL(*tmpRight);

		return &left;
	}

	template <typename Key, size_t Deg> requires MinDeg<Deg>
	bool DataNode<Key, Deg>::verify(Owner* pOwner, InnNode* pParent)
	{
		if (!_ppOwner || !*_ppOwner || *_ppOwner != pOwner)
			return false;

		if (!_ppParent || !_ppLeft || !_ppRight || !_ppSelf)
			return false;

		if (*_ppParent != pParent)
			return false;

		if (!pParent)
			return false;

		if (*_ppSelf != this)
			return false;
		
		return true;
	}

	template <typename Key, size_t Deg> requires MinDeg<Deg>
	InnNode<Key, Deg>::InnNode(POwnerPtr ppOwner)
	{
		_ppOwner = ppOwner;
		_ppParent = std::make_shared<InnNode*>();
		_ppLeft = std::make_shared<DataNode*>();
		_ppRight = std::make_shared<DataNode*>();
	}

	template <typename Key, size_t Deg> requires MinDeg<Deg>
	InnNode<Key, Deg>::~InnNode()
	{
		if (_ppSelf)
			*_ppSelf = NULL;
	}

	template <typename Key, size_t Deg> requires MinDeg<Deg>
	auto InnNode<Key, Deg>::find(const Key& k)->std::pair<DataListIt, bool>
	{
		auto it = _data.begin();
		while (it != _data.end() && (*it)->_k < k)
			++it;

		bool ret = it == _data.end() ? false : (*it)->_k == k;
		return std::make_pair(it, ret);
	}

	template <typename Key, size_t Deg> requires MinDeg<Deg>
	auto InnNode<Key, Deg>::insert(const Key& k)->std::pair<DataListIt, bool>
	{
		auto [it, ret] = find(k);
		if (ret)
			return std::make_pair(it, false);

		if (_data.size() >= DataMax<Deg>)
			return split(k, it);

		if (_leaf)
			return insertNonFull(k, it);

		return getNextNode(it)->insert(k);
	}

	template <typename Key, size_t Deg> requires MinDeg<Deg>
	auto InnNode<Key, Deg>::insertNonFull(const Key& k, DataListIt it)->std::pair<DataListIt, bool>
	{
		auto newIt = _data.insert(it, new DataNode(_ppOwner));
		DataNode* pNewData = *newIt;
		pNewData->_ppParent = _ppSelf;
		pNewData->_id = newIt;
		pNewData->_k = k;

		if (it != _data.end())
			pNewData->_ppRight = (*it)->_ppLeft;

		auto rIt = std::make_reverse_iterator(newIt);
		if (rIt != _data.rend())
			pNewData->_ppLeft = (*rIt)->_ppRight;

		return std::make_pair(newIt, true);
	}

	template <typename Key, size_t Deg> requires MinDeg<Deg>
	auto InnNode<Key, Deg>::split(const Key& k, DataListIt it)->std::pair<DataListIt, bool>
	{
		InnNode* pUpNode = *_ppParent;
		if (!pUpNode)
		{
			pUpNode = new InnNode(_ppOwner);
			pUpNode->_ppSelf = std::make_shared<InnNode*>(pUpNode);
			pUpNode->_leaf = false;
			_ppParent = pUpNode->_ppSelf;
			(*_ppOwner)->_root = pUpNode;
		}

		DataListIt insertIt = *_ppRight ? (*_ppRight)->_id : pUpNode->_data.end();
		DataListIt splitIt = std::next(_data.begin(), SplitDeg<Deg>);
		std::pair<DataListIt, bool> ret = _leaf ? insertNonFull(k, it) : getNextNode(it)->insert(k);
		DataListIt rightIt = std::next(splitIt, 1);
		pUpNode->_data.splice(insertIt, _data, splitIt);
		DataNode* pSplitNode = *splitIt;
		pSplitNode->_ppParent = pUpNode->_ppSelf;
		if (*pSplitNode->_ppLeft)
			(*pSplitNode->_ppLeft)->_ppRight = std::make_shared<DataNode*>();

		pSplitNode->_ppLeft = _ppSelf;

		if (*_ppRight)
			(*_ppRight)->_ppLeft = std::make_shared<InnNode*>();

		if (*pSplitNode->_ppRight)
			(*pSplitNode->_ppRight)->_ppLeft = std::make_shared<DataNode*>();

		pSplitNode->_ppRight = _ppRight && *_ppRight ? (*_ppRight)->_ppLeft : std::make_shared<InnNode*>();

		InnNode* pRightNode = new InnNode(_ppOwner);
		pRightNode->_ppParent = _ppParent;
		pRightNode->_ppSelf = pSplitNode->_ppRight;
		*pRightNode->_ppSelf = pRightNode;
		pRightNode->_ppLeft = pSplitNode->_ppSelf;
		pRightNode->_ppRight = _ppRight;
		_ppRight = pSplitNode->_ppSelf;
		pRightNode->_leaf = _leaf;
		pRightNode->_data.splice(pRightNode->_data.begin(), _data, rightIt, _data.end());
		bool first = true;
		for (auto pNode : pRightNode->_data)
		{
			pNode->_ppParent = pRightNode->_ppSelf;
			if (*pNode->_ppRight)
				(*pNode->_ppRight)->_ppParent = pRightNode->_ppSelf;

			if (!first)
				continue;

			first = false;
			if (*pNode->_ppLeft)
				(*pNode->_ppLeft)->_ppParent = pRightNode->_ppSelf;
		}

		return ret;
	}

	template <typename Key, size_t Deg> requires MinDeg<Deg>
	auto InnNode<Key, Deg>::erase(const Key& k)->std::pair<DataListIt, bool>
	{
		if (_data.empty())
			return std::make_pair(DataListIt(), false);

		auto [it, ret] = find(k);
		if (ret)
			return erase(it);

		if (_leaf)
			return std::make_pair(DataListIt(), false);

		bool isRight = it == _data.end();
		DataNode& dataNode = isRight ? **_data.rbegin() : **it;
		InnNode& nextNode = isRight ? **dataNode._ppRight : **dataNode._ppLeft;
		if (nextNode._data.size() > SplitDeg<Deg>)
			return nextNode.erase(k);

		InnNode& broNode = isRight ? **dataNode._ppLeft : **dataNode._ppRight;
		if (broNode._data.size() < Deg)
		{
			auto pMergeNode = dataNode.merge();
			if (_data.size())
				return pMergeNode->erase(k);

			return (*_ppOwner)->erase(k, pMergeNode);
		}

		DataNode& nextDataNode = isRight ? **nextNode._data.begin() : **nextNode._data.rbegin();
		DataNode& broDataNode = isRight ? **broNode._data.rbegin() : **broNode._data.begin();

		broDataNode._ppParent = _ppSelf;
		dataNode._ppParent = nextNode._ppSelf;
		if (isRight)
		{
			if (*dataNode._ppLeft)
				(*dataNode._ppLeft)->_ppRight = broDataNode._ppSelf;
			broDataNode._ppLeft = dataNode._ppLeft;
			dataNode._ppLeft = broDataNode._ppRight;
			if (*dataNode._ppLeft)
				(*dataNode._ppLeft)->_ppRight = dataNode._ppSelf;
			broDataNode._ppRight = nextNode._ppSelf;

			dataNode._ppRight = nextDataNode._ppLeft;
			nextDataNode._ppLeft = _ppSelf;
			nextNode._ppLeft = broDataNode._ppSelf;

			_data.splice(_data.end(), broNode._data, broDataNode._id);
			nextNode._data.splice(nextNode._data.begin(), _data, dataNode._id);
		}
		else
		{
			if (*dataNode._ppRight)
				(*dataNode._ppRight)->_ppLeft = broDataNode._ppSelf;
			broDataNode._ppRight = dataNode._ppRight;
			dataNode._ppRight = broDataNode._ppLeft;
			if (*dataNode._ppRight)
				(*dataNode._ppRight)->_ppLeft = dataNode._ppSelf;
			broDataNode._ppLeft = nextNode._ppSelf;

			dataNode._ppLeft = nextDataNode._ppRight;
			nextDataNode._ppRight = _ppSelf;
			nextNode._ppRight = broDataNode._ppSelf;

			_data.splice(_data.begin(), broNode._data, broDataNode._id);
			nextNode._data.splice(nextNode._data.end(), _data, dataNode._id);
		}

		return nextNode.erase(k);
	}

	template <typename Key, size_t Deg> requires MinDeg<Deg>
	auto InnNode<Key, Deg>::erase(DataListIt it)->std::pair<DataListIt, bool>
	{
		if (_leaf)
		{
			DEL(*it);
			auto nextIt = _data.erase(it);
			return std::make_pair(nextIt, true);
		}

		DataNode& swapEraseNode = **it;
		InnNode& leftNode = **swapEraseNode._ppLeft;
		if (leftNode._data.size() > SplitDeg<Deg>)
		{
			DataListIt eraseIt = std::prev(leftNode._data.end());
			swapEraseNode._k =(*eraseIt)->_k;
			return leftNode.erase(eraseIt);
		}

		InnNode& rightNode = **swapEraseNode._ppRight;
		if (rightNode._data.size() > SplitDeg<Deg>)
		{
			DataListIt eraseIt = rightNode._data.begin();
			swapEraseNode._k = (*eraseIt)->_k;
			return rightNode.erase(eraseIt);
		}

		return swapEraseNode.merge()->erase(it);
	}


	template <typename Key, size_t Deg> requires MinDeg<Deg>
	template <typename Func>
	auto InnNode<Key, Deg>::show(std::ostream& os, Func func) const->std::ostream&
	{
		bool first = true;
		os << "[";
		for (auto& pPt : _data)
		{
			if (first) first = false;
			else os << ",";

			os << pPt->_k;
		}
		os << "]";
		if (_leaf)
			return os;

		os << "={";
		first = true;
		bool left = true;
		for (auto& pPt : _data)
		{
			do
			{
				if (!left)
					break;

				left = false;
				if (!*pPt->_ppLeft)
					break;

				first = false;
				(*pPt->_ppLeft)->show(os, func);
			} while (false);

			if (!*pPt->_ppRight)
				continue;

			if (first) first = false;
			else os << ",";

			(*pPt->_ppRight)->show(os, func);
		}
		return os << "}";
	}


	template <typename Key, size_t Deg> requires MinDeg<Deg>
	bool InnNode<Key, Deg>::verify(Owner* pOwner, InnNode* pParent)
	{
		if (!_ppOwner || !*_ppOwner || *_ppOwner != pOwner)
			return false;

		if (!_ppParent || !_ppLeft || !_ppRight || !_ppSelf)
			return false;

		if (*_ppParent != pParent)
			return false;

		if (*_ppSelf != this)
			return false;

		if (!pParent)
		{
			if (pOwner->_root != this)
				return false;
		}
		else
		{
			if (!*_ppLeft && !*_ppRight)
				return false;

			if (*_ppLeft)
			{
				if (!(*_ppLeft)->_ppRight)
					return false;

				if (*(*_ppLeft)->_ppRight != this)
					return false;
			}

			if (*_ppRight)
			{
				if (!(*_ppRight)->_ppLeft)
					return false;

				if (*(*_ppRight)->_ppLeft != this)
					return false;
			}
		}

		bool first = true;
		for (DataNode* pNode :_data)
		{
			if (!pNode->verify(pOwner, this))
				return false;

			if (_leaf)
				continue;

			if (!pNode->_ppRight)
				return false;

			if (!*pNode->_ppRight)
				return false;

			if (!(*pNode->_ppRight)->verify(pOwner, this))
				return false;

			if (!first)
				continue;
			
			first = false;
			if (!pNode->_ppLeft)
				return false;

			if (!*pNode->_ppLeft)
				return false;

			if (!(*pNode->_ppLeft)->verify(pOwner, this))
				return false;
		}

		return true;
	}

	template <typename Key, size_t Deg> requires MinDeg<Deg>
	auto InnNode<Key, Deg>::getNextNode(DataListIt it)->InnNode*
	{
		PInnNodePtr ppNextNode = it != _data.end() ? (*it)->_ppLeft : (*_data.rbegin())->_ppRight;

		InnNode*& pNextNode = *ppNextNode;
		if (pNextNode)
			return pNextNode;

		pNextNode = new InnNode(_ppOwner);
		pNextNode->_ppParent = _ppSelf;
		pNextNode->_ppSelf = ppNextNode;
		pNextNode->_ppRight = it != _data.end() ? (*it)->_ppSelf : std::make_shared<DataNode*>();
		auto rIt = std::make_reverse_iterator(it);
		pNextNode->_ppLeft = rIt != _data.rend() ? (*rIt)->_ppSelf : std::make_shared<DataNode*>();

		return pNextNode;
	}
}